//#include<iostream>
//#include<vector>
//using namespace std;
//
//
/////////动态规划 建立lmax和rmax数组分别表示 i处左侧和右侧最高的柱子
///////// 遍历i由0到len-1依次计算每处i存水的值 
//int trap(vector<int>& height) {
//    int len = height.size();
//    vector<int> lmax(len, 0);
//    vector<int> rmax(len, 0);
//    int result = 0;
//    for (int i = 0; i < len; i++)
//    {
//        if (i == 0)
//        {
//            lmax[i] = height[i];
//        }
//        else
//            lmax[i] = max(lmax[i - 1], height[i]);
//    }
//    for (int i = len - 1; i >= 0; i--)
//    {
//        if (i == (len - 1))
//        {
//            rmax[i] = height[i];
//        }
//        else
//            rmax[i] = max(rmax[i + 1], height[i]);
//    }
//    for (int i = 1; i < len - 1; i++)
//    {
//        int high = min(lmax[i], rmax[i]);
//        result += high - height[i];
//    }
//    return result;
//}
//
//int main()
//{
//    vector<int> height = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };     ///存6格雨水
//    cout<<trap(height)<<endl;
//}